#!/usr/bin/env python2.5

import random

class Node(object):
   left, right = None, None

   def __init__(self, Address = None):
      self._parent = None
      self._child = []
      self._nodeid = random.randint(1000, 5000)
      self._addrid = 0
      self._address = None

      if Address:
         self.address = Address

   def setparent(self, Parent):
      if isinstance(Parent, Node):
         self.parent = Parent

   def addchild(self, Child):
      if isinstance(Child, Node):
         self.child.append(Child)

   def __int__(self):
      return self.nodeid

   def value(self):
      return self.addrid

   def ipaddr(self):
      return self.address

   def __contains__(self, Address):
      retval = False
      if self.address and Address in self.address:
         retval = True

      return retval

   def __getitem__(self, Id):
      if int(Id) == self.addrid:
         return self.address

   def __iter__(self):
      for ix in self.child:
         yield ix.address

   def children(self):
      retval = []
      for ix in self.child:
         retval.append(str(ix.ipaddr()))

      return retval

class tree(object):
   def __init__(self):
      self.root = None

   def addNode(self, Id, Address = None):
      return Node(Id, Address)

   def insert(self, root, Id, Address):
      retval = None
      if root == None:
         retval = self.addNode(Id, Address)
      else:
         if Address in root:
            root.left = self.insert(root.left, Id, Address)
         else:
            root.right = self.insert(root.right, Id, Address)

         retval = root

      return retval

   def lookup(self, root, target):
      retval = None
      if root:
         if target == root.value():
            retval = root
         else:
            if target < root.value():
               retval = self.lookup(root.left, target)
            else:
               retval = self.lookup(root.right, target)

      return retval

   def depth(self, root):
      retval = 0
      if root:
         left = self.depth(root.left)
         right = self.depth(root.right)

         retval = max(left, right) + 1

      return retval

   def size(self, root):
      retval = 0
      if root:
         retval = self.size(root.left) + 1 + self.size(root.right)

      return retval
